#include "thread.h"

extern func_BiTree fBiTree;

/**
 *  功 能：
 *      线索化二叉树 -- 中序线索化
 *  参 数：
 *      root：要线索化的树的根节点
 *      ptmp：用于保留前驱节点
 *  返回值：
 *      无
 **/
void in_thread(BiTNode *root, BiTNode **ptmp)
{
    if ((root == NULL))
        goto END;

    in_thread(root->lchild, ptmp);

    if (root->lchild == NULL)
    {
        root->lchild = *ptmp;
        root->lTag = 1;
    }
    if (*ptmp != NULL && (*ptmp)->rchild == NULL)
    {
        (*ptmp)->rchild = root;
        (*ptmp)->rTag = 1;
    }

    (*ptmp) = root;
    in_thread(root->rchild, ptmp);
END:
    return;
}

/**
 *  功 能：
 *      中序线索化二叉树的后继节点 
 *  参 数：
 *      root：要查找的节点
 *  返回值：
 *      成功：节点的后继节点
 *      失败：NULL
 **/
BiTNode *in_thread_nextNode(BiTNode *root)
{
    BiTNode *ret = NULL;

    if (root == NULL)
        goto END;

    if (root->rTag == 1) // 右标志位 1，可以直接得到后继节点
    {
        ret = root->rchild;
    }
    else // 右标志位0，则要找到右子树最左下角的节点
    {
        ret = root->rchild;
        while (ret->lTag == 0) // 查找最左下节点的位置
        {
            ret = ret->lchild;
        }
    }

END:
    return ret;
}

/**
 *  功 能：
 *      中序线索化二叉树的前驱节点 
 *  参 数：
 *      root：要查找的节点
 *  返回值：
 *      成功：节点的后继节点
 *      失败：NULL
 **/
BiTNode *in_thread_prevNode(BiTNode *root)
{
    BiTNode *ret = NULL;

    if (root == NULL)
        goto END;

    if (root->lTag == 1) // 左标志位 1，可以直接得到前驱节点
    {
        ret = root->lchild;
    }
    else // 左标志位0
    {
        ret = root->lchild;
        while (ret->rTag == 0) // 查找最右下节点的位置
        {
            ret = ret->rchild;
        }
    }

END:
    return ret;
}

/**
 *  功 能：
 *      遍历线索化二叉树 - 中序正常顺序
 *  参 数：
 *      root：要遍历的线索二叉树的根节点
 *  返回值：
 *      无
 **/
void in_thread_Older_next(BiTNode *root)
{
    if (root == NULL)
        goto END;

    while (root->lTag == 0) // 查找中序遍历的第一个节点，当lTag == 0的话
        root = root->lchild;

    printf("%c ", root->data); // 访问第一个节点

    while (root->rchild != NULL) // 当root存在后继，依次访问后继节点
    {
        root = in_thread_nextNode(root);
        printf("%c ", root->data);
    }

END:
    printf("\n");
    return;
}

/**
 *  功 能：
 *      遍历线索化二叉树 - 倒序输出
 *  参 数：
 *      root：要遍历的线索二叉树的根节点
 *  返回值：
 *      无
 **/
void in_thread_Older_prev(BiTNode *root)
{
    if (root == NULL)
        goto END;

    BiTNode *post = in_thread_nextNode(root);

    while (post->rchild != NULL) // 查找中序遍历的最后一个节点
        post = in_thread_nextNode(post);

    while (post) // 当post不为NULL，依次访问前驱节点
    {
        printf("%c ", post->data);
        post = in_thread_prevNode(post);
    }

    post = NULL;

END:
    printf("\n");
    return;
}

funThread fthread = {
    in_thread,

    in_thread_Older_next,
    in_thread_Older_prev,

    in_thread_nextNode,
    in_thread_prevNode,
};
